public class SolutionOffer42 {
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        int last=nums[0];
        int max=last;
        for (int i=1;i<n;i++){
            last=last<0?nums[i]:last+nums[i];
            max=Math.max(max,last);
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(new SolutionOffer42().maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }
}
